package main

import (
    "fmt"
    "time"
)

func solveNQueens(n int) [][]string {
    solutions := [][]string{}
    queens := make([]int, n)
    for i := range queens {
        queens[i] = -1
    }
    columns := make(map[int]bool)
    diagonal1 := make(map[int]bool)
    diagonal2 := make(map[int]bool)

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            board := generateBoard(queens, n)
            solutions = append(solutions, board)
            return
        }

        for i := 0; i < n; i++ {
            if columns[i] || diagonal1[row-i] || diagonal2[row+i] {
                continue
            }

            queens[row] = i
            columns[i] = true
            diagonal1[row-i] = true
            diagonal2[row+i] = true
            backtrack(row + 1)
            columns[i] = false
            diagonal1[row-i] = false
            diagonal2[row+i] = false
        }
    }

    backtrack(0)
    return solutions
}

func generateBoard(queens []int, n int) []string {
    board := make([]string, n)
    for i := 0; i < n; i++ {
        row := make([]byte, n)
        for j := 0; j < n; j++ {
            row[j] = '.'
        }
        row[queens[i]] = 'Q'
        board[i] = string(row)
    }
    return board
}

func main() {
    t1 := time.Now()
    solutionsArray := []int{}
    for i := 0; i < 15; i++ {
        solutionsText := solveNQueens(i)
        solutionsArray = append(solutionsArray, len(solutionsText))
    }
    fmt.Println(solutionsArray[len(solutionsArray)-1])
    fmt.Println(time.Since(t1))
}